package com.yifan.leetcode.dataStructure;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @Author YIFan
 * @Date 2023-2-4 15:33
 * @Version 1.0、
 * <p>
 * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * <p>
 * 子数组 是数组中的一个连续部分。
 * <p>
 * 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
 * 输出：6
 * 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
 */
public class 最大子数组和 {

    public static void main(String[] args) {
        /* -2,1,-3,4,-1,2,1,-5,4 */
//        System.err.println(最大子数组和.max(new int[]{-1,0,-2}));
        System.err.println(最大子数组和.max1(new int[]{-2, -1, -3, -4, -1, -2, -1, -5, -4}));
    }

    public static int max(int[] nums) {
        List<Integer> list = Arrays.stream(nums).boxed().collect(Collectors.toList());
        for (int i = 0; i < nums.length & nums.length > 1; i++) {
            int temp = nums[i];
            for (int j = i + 1; j < nums.length; j++) {
                temp = temp + nums[j];
                list.add(temp);
            }
        }
        return Collections.max(list);
    }

    /*动态规划*/
    /*理解： 若前一个元素大于0，则加道当前元素*/
    /*原 -2,1,-3,4,-1,2,1,-5,4 */
    /*新 -2,1,-2,4,3,5,6,1,5 */
    public static int max1(int[] nums) {
        ArrayList<Integer> list = new ArrayList<>();
        int temp = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i == 0) {
                temp = nums[0];
                list.add(temp);
            } else {
                if (temp>0){
                    temp = nums[i] + temp;//当前元素 + 前一个元素
                }else {
                    temp = nums[i];
                }
                list.add(temp);
            }
        }
        return Collections.max(list);
    }

}
